'''
https://leetcode.cn/problems/critical-connections-in-a-network/?envType=study-plan-v2&envId=graph-theory
'''
from typing import List


class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n)]
        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)

        res = []

        dfn = [-1] * n
        low = [n] * n
        id = 1
        def f(u, parent):
            nonlocal id
            dfn[u], low[u] = id, id
            id += 1
            for v in graph[u]:
                if parent == v: continue    # 访问过v,且防止v是另一个环上的节点
                if dfn[v] == -1:        # 没访问过v
                    f(v, u)
                    low[u] = min(low[u], low[v])
                else:                   # 访问过v
                    low[u] = min(low[u], dfn[v])
            if parent != -1 and low[u] == dfn[u]:
                res.append([u, parent])
        f(0, -1)
        return res

n = 4
connections = [[0,1],[1,2],[2,0],[1,3]]
print(Solution().criticalConnections(n, connections))